package com.fwpsl.tree;

/**
 * @author: 风戏fw
 * @date: 2024/3/26
 * @description: 平衡二叉树： 在满足查找二叉树的大小规则下，让树尽可能矮小，以此来提高查数据的性能。
 * 要求：任意节点的左右个子树的高度差不超过1，任意节点的左右两个子树都是一个平衡二叉树。
 * 旋转的四种情况：左左LL（右旋）、左右LR（先左旋变成左左，再右旋）、右右RR（左旋）、右左RL（先右旋变成右右，再左旋）。
 * <p>
 * AVL树是一种自平衡的二叉搜索树，它的特点是每个节点的左子树和右子树的高度差最多为1。
 * 这种平衡条件保证了AVL树的操作，如插入、删除和搜索，具有对数时间复杂度。
 * 当向AVL树中插入或删除节点时，如果破坏了树的平衡状态，就需要通过旋转操作来恢复树的平衡。
 */
public class AVLTree<T extends Comparable<T>> {

    class Node<T extends Comparable<T>> extends Tree.Node {

        /**
         * 树高
         */
        protected int height;

        public Node(T val) {
            super(val);
            this.height = 1; // 新节点的高度为1
        }

        public int getHeight() {
            return height;
        }

        public void setHeight(int height) {
            this.height = height;
        }

        @Override
        public T getVal() {
            return (T) super.getVal();
        }

        @Override
        public Node<T> getLeft() {
            return (Node<T>) super.getLeft();
        }

        @Override
        public Node<T> getRight() {
            return (Node<T>) super.getRight();
        }
    }

    private Node<T> root;

    /**
     * 获取节点高度
     *
     * @param node
     * @return
     */
    private int getHeight(Node<T> node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    /**
     * 更新节点高度
     *
     * @param node
     */
    private void updateHeight(Node<T> node) {
        int leftHeight = getHeight(node.getLeft());
        int rightHeight = getHeight(node.getRight());
        node.height = Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 获取平衡因子
     *
     * @param node
     * @return
     */
    private int getBalanceFactor(Node<T> node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.getLeft()) - getHeight(node.getRight());
    }

    /**
     * 右旋
     *
     * @param y
     * @return
     */
    private Node<T> rightRotate(Node<T> y) {
        Node<T> x = y.getLeft();
        Node<T> T2 = x.getRight();

        x.setRight(y);
        y.setLeft(T2);

        updateHeight(y);
        updateHeight(x);

        return x;
    }

    /**
     * 左旋
     *
     * @param x
     * @return
     */
    private Node<T> leftRotate(Node<T> x) {
        Node<T> y = x.getRight();
        Node<T> T2 = y.getLeft();

        y.setLeft(x);
        x.setRight(T2);

        updateHeight(x);
        updateHeight(y);

        return y;
    }

    /**
     * 插入节点
     *
     * @param node
     * @param value
     * @return
     */
    private Node<T> insert(Node<T> node, T value) {
        if (node == null) {
            return new Node<>(value);
        }

        if (value.compareTo(node.getVal()) < 0) {
            node.left = insert(node.getLeft(), value);
        } else if (value.compareTo(node.getVal()) > 0) {
            node.right = insert(node.getRight(), value);
        } else {
            // 值相同，不插入
            return node;
        }

        updateHeight(node);

        int balanceFactor = getBalanceFactor(node);

        // LL情况
        if (balanceFactor > 1 && value.compareTo(node.getLeft().getVal()) < 0) {
            return rightRotate(node);
        }
        // RR情况
        if (balanceFactor < -1 && value.compareTo(node.getRight().getVal()) > 0) {
            return leftRotate(node);
        }
        // LR情况
        if (balanceFactor > 1 && value.compareTo(node.getLeft().getVal()) > 0) {
            node.left = leftRotate(node.getLeft());
            return rightRotate(node);
        }
        // RL情况
        if (balanceFactor < -1 && value.compareTo(node.getRight().getVal()) < 0) {
            node.right = rightRotate(node.getRight());
            return leftRotate(node);
        }

        return node;
    }

    /**
     * 插入新值
     *
     * @param value
     */
    public void insert(T value) {
        root = insert(root, value);
    }

    public static void main(String[] args) {
        AVLTree<Integer> avlTree = new AVLTree<>();
        // 插入一些值
        avlTree.insert(10);
        avlTree.insert(20);
        avlTree.insert(30);
        avlTree.insert(40);
        avlTree.insert(50);
        avlTree.insert(25);

        // 中序遍历
        TreeTraversal.inorderTraversal(avlTree.root);
        System.out.println();

        System.out.println("AVL tree constructed with the given values.");
    }
}
